public class Solution {
    public static ListNode insertionSortList(ListNode head) {
        if(head == null)
            return head;
        ListNode minHead = new ListNode(Integer.MIN_VALUE);
        ListNode last = head;
        while(last != null) {
            ListNode nextNode = last.next;
            ListNode insertNode = minHead;
            while(insertNode.next != null) {
                if(last.val < insertNode.next.val)
                    break;
                insertNode = insertNode.next;
            }
            last.next = insertNode.next;
            insertNode.next = last;
            last = nextNode;
        }
        return minHead.next;
    }
}